/* Queue using Linked List - Program to create a queue ADT using linked list. ADT should support the following operations
1)  Createqueue
2)  Insert into the queue
3)  Delete from the queue
4)  destroyqueue
*/

/* queue q declared globally */

#include <stdio.h>
#include <stdlib.h>
#define NULL 0	

struct  node
{
  int  data ;
  struct  node  *next ;
} ;

struct  queue
{
 struct  node  *front , *rear ;
} ;

struct  queue  q ;

/* This function initializes the queue to empty by making both front and rear as NULL */
void createqueue()
{
  q.front=q.rear=NULL ;
}

int  empty()
{
  if(q.front==NULL)
    return  1 ;
  else
    return  0 ;
}

void  insert(int  x)
{
  struct  node  *pnode ;

  pnode=(struct node*)malloc(sizeof(struct node)) ;
  if(pnode==NULL)
  {
    printf("Memory overflow. Unable to insert.\n") ;
    exit(1) ;
  }

  pnode->data=x ;
  pnode->next=NULL ;   /* New node is always last node */

  if(empty())
      q.front=q.rear=pnode ;
  else
  {
      (q.rear)->next=pnode ;
      q.rear=pnode ;
  }
}

int  removes()
{
  int  x ;
  struct  node  *p ;

  if(empty())
  {
    printf("Queue Underflow. Unable to remove.\n") ;
    exit(1) ;
  }

  p=q.front ;
  x=(q.front)->data ;
  q.front=(q.front)->next ;
  if(q.front==NULL)       /* Queue contained only one node */
       q.rear=NULL ;
  free(p) ;
  return  x ;
}

void  show()
{
  struct  node  *p ;

  if(empty())
    printf("Queue empty. No data to display \n") ;
  else
  {
    printf("Queue from front to rear is as shown: \n") ;

    p=q.front ;
    while(p!=NULL)
    {
      printf("%d ",p->data) ;
      p=p->next ;
    }

    printf("\n") ;
  }
}

void  destroyqueue()
{
  q.front=q.rear=NULL ;
}

int main()
{
  int  x , ch ;

  createqueue() ;

  do
  {
    printf("\n\n  Menu: \n") ;
    printf("1:Insert \n") ;
    printf("2:Remove \n") ;
    printf("3:exit \n") ;
    printf("Enter your choice: ") ;
    scanf("%d",&ch) ;

    switch(ch)
    {
      case 1:
      printf("Enter element to be inserted: ") ;
      scanf("%d",&x) ;
      insert(x) ;
      show() ;
      break ;

      case 2:
      x=removes() ;
      printf("Element removed is: %d\n",x) ;
      show() ;
      break ;

      case 3:
      break ;
    }
  }
  while(ch!=3) ;

  destroyqueue() ;

 return 0;
}
